package Algorithm;

import java.util.*;

 class ListNode {
     int val;
     ListNode next = null;

    ListNode(int val) {
         this.val = val;
    }
}


public class Work3 {
    /*链表相关的题*/
    /*1:从尾到头打印链表
    * 解题思路:
    * 1:使用栈
    * 2:使用数组,逆序数组
    * 3:递归,
    * 注12,太简单就不写了,直接写3*/

    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        Stack<Integer> st = new Stack<>();
        while(listNode != null){
            st.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        while(!st.empty()){
            list.add(st.pop());
        }
        return list;
    }


    //方法二，逆置数组
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while(listNode != null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        int i = 0;
        int j = list.size() - 1;
        while(i < j){
            Integer temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
            i++;
            j--;
        }
        return list;
    }

    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        ArrayList<Integer> arrayList=new ArrayList<>();
        if (listNode == null){
            return arrayList;
        }
        printListFromTailToHeadFunc(listNode,arrayList);
        return arrayList;

    }
    private void printListFromTailToHeadFunc(ListNode listNode,ArrayList<Integer> arrayList) {
        if (listNode == null){
            return ;
        }
        printListFromTailToHeadFunc(listNode.next,arrayList);
        arrayList.add(listNode.val);
    }
    /*输入一个链表，输出该链表中倒数第k个结点*/
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k < 0){
            return null;
        }
        ListNode front = head;
        ListNode rear = head;
        while(k > 0 && front != null){
            k--;
            front = front.next;
        }
        while(front != null){
            front = front.next;
            rear = rear.next;
        }
        return k > 0 ? null : rear;
    }
    /*反转链表
    * 解题思路:三指针*/
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode left = head;
        ListNode mid =left.next;
        ListNode right = mid.next;
        //要考虑边界问题-正常情况
        while (right != null){
            mid.next = left;
            left = mid;
            mid = right;
            right = right.next;
        }
        //双指针进行反转
        mid.next=left;
        //断开头结点
        head.next=null;
        head=mid;
        return head;
    }
    public ListNode ReverseList2(ListNode head) {
        //给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
        //解法：头插法
        if (head == null){
            return null;
        }
        if (head.next == null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while (cur !=null){
            ListNode curNext= cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
    /*合并两个排序的链表
    * 解题思路:
    * 1:利用一个新的头结点,依次排序插入,归并思想
    * 2:递归的去实现*/
    public ListNode Merge1(ListNode list1,ListNode list2) {
        /*归并写法*/
        /*判断空值情况*/
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        ListNode newHead=new ListNode(-1);
        /*注意:如果newHead不带新节点,而是赋值为空,那么接下来的循环就要先
        * 判定头结点是否为空然后赋值,在继续接下来的判断*/
        ListNode p1=list1;
        ListNode p2=list2;
        ListNode cur=newHead;
        //比较依次插入
        while (p1 !=null && p2 != null){
            if (p1.val < p2.val){
                cur.next=p1;
                p1=p1.next;
                cur=cur.next;
            }else {
                cur.next=p2;
                p2=p2.next;
                cur=cur.next;
            }
        }
        //判断是否有剩余.
        if (p1 != null){
            cur.next=p1;
        }
        if (p2 != null){
            cur.next=p2;
        }
        return newHead.next;
    }
    public ListNode Merge2(ListNode list1,ListNode list2) {
        /*递归解法*/
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        ListNode newHead=null;
        //找到头结点,并删除已经找到的节点.
        if (list1.val > list2.val){
            newHead = list2;
            list2 = list2.next;
        }else {
            newHead = list1;
            list1 = list1.next;
        }
        newHead.next = Merge2(list1,list2);
        return newHead;
    }



    /*删除链表中重复的结点：重复节点不保留*/
    public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null){
            return pHead;
        }
        ListNode head = new ListNode(0);
        head.next = pHead;
        ListNode prev = head;
        ListNode last = prev.next;
        while(last != null){//last永远在前面
            //先找到重复的开始
            while(last.next != null && last.val != last.next.val){
                prev = prev.next;
                last = last.next;
            } //在找到重复的范围
            while(last.next != null && last.val == last.next.val){
                last = last.next;
            } //走到这里结果一共有三种,注意：prev永远指向的是前驱有效起始节点：
            //1. last.next != null 并且 (prev, last] 限定了一段重复范围，此时进行去重
            //2. last.next == null && (prev, last] 限定了一段重复范围，此时进行去重，最后相当于prev->next = nullptr
            //3. last.next == null && prev.next == last,这说明，从本次循环开始，大家都不相同，就不需要进行去重，这个是特殊情况
            if(prev.next != last){//说明是一段范围，可以去重
                prev.next = last.next;
            }
            last = last.next; //走这一步，就是为了保证恢复的和最开始一致
        }
        return head.next;
    }




}
